Various techniques are used to identify items (e.g., products, music, movies, hotel rooms, flights, etc.) to recommend to a user in which the user is likely to be most interested. For example, a product sales website will present a few recommended products for a user shopping on the website. Some techniques provide general recommendations applicable to all users, for example, identifying the website's top 5 current products based on purchases made by all users. However, such general recommendations do a poor job of identifying the individual users' interests. Thus, various techniques attempt to identify items that are better tailored to a user based on information about the user and other users. Specifically, collaborative filtering techniques (also known as social filtering techniques) use the assumption that users who were previously interested in the same items are likely to have similar interests on other items.
Existing collaborative filtering techniques that attempt to identify items to recommend to users are unable to provide adequate recommendations in large scale, one class (i.e., positive interest feedback only) environments. Positive interest feedback environments are common in Internet and other network-based applications. For example, many websites offer products for sale and collect information about millions of users purchasing millions of products. The providers of such websites can identify positive interest of users in items based on the purchases that the users make, but cannot similarly identify that users have negative interest in items based on the users not having purchased the items. As a specific example, when a user views a product information web page about a book for sale and then purchases the book, it is known that the user has a positive interest in the book. However, if the user views the product information web page about the book and does not purchase the book or never views the product information web page about the book, it does not necessarily mean that the user has a negative opinion of the book. Existing collaborative filtering techniques are unable to make recommendations in these environments with sufficient relevancy and efficiency.